1. Technical Field
The present invention is related generally to an improved data processing system and, more particularly, to an improved first in last out data structure within a memory array.
2. Description of Related Art
A stack or First In Last Out (FILO) data structure is used in many computer applications. Often multiple stacks are needed in a single application and they are added on an as needed basis because, at the beginning of the application, it is not known how many stacks will be needed. Since memory in computer systems is arranged as a linear array, the application will have some segment of this linear array that it will use to place multiple stacks. The way stacks are traditionally implemented is with a base and head pointer. A stack with five elements growing to the right is shown in FIG. 1A. FIG. 1B shows the same stack as in FIG. 1A with 10 elements. FIG. 2A depicts a stack with five elements that grows to the left. As more elements are added to the stack, the head moves in memory to the left as depicted in FIG. 2B where the head has moved to element 9.
In an application, the first stack is chosen to be either a right or a left growing stack and is placed at the opposite end of the linear array from the direction of stack growth. Thus, if the first stack is a right growing stack, then the first element in the stack is placed at the left end of the memory array. For this discussion, assume that a right growing stack is chosen first. If an additional stack is then needed, the additional stack is chosen to be a left growing stack and is placed in the right of the array. Thus, we end with the situation depicted in FIG. 3 where the first stack 302 is a right growing stack placed at the left end of the memory array 300 and the second stack 304 is a left growing stack placed at the right end of the memory array 300.
In the case depicted in FIG. 3, in which two stacks are placed at opposite ends of the memory array 300, each stack 302-304 may grow until it hits the opposite stack coming from the opposite direction (which is referred to as a collision). This case is considered to be very efficient because, if all the stacks 302-304 grow at the same rate, all memory within the memory array 300 will be consumed before a collision. However, if a third stack is needed, a dilemma is encountered. The third stack can be placed in the middle of the first two stacks as depicted in FIG. 4, thus leaving room for a fourth stack. However, if the application does not need a fourth stack, stack #3402 will collide with stack #2304 long before stack #1302 has used all its space.
It has been shown that with this method of laying out stacks, even numbers of stacks are more efficient at using the given memory array space that are odd numbers of stacks. Thus, if the application happens to favor an odd number of stacks, the application will not use memory efficiently. Therefore, a method of organizing stacks within a memory array that utilizes available memory space more efficiently for both odd and even numbers of stacks is desirable.